I. Field of the Invention
The present invention relates to a system and method for creating random sequences. More specifically, embodiments of the present invention relate to a system and method for combining two or more random elemental sequences to form a random combinational sequence. This combinational sequence can be used to encrypt or decrypt messages (or any other type of information). The present invention allows the elemental sequences to be efficiently utilized so that substantial amounts of combinational sequence can be created while at the same time precluding the combinational sequence from being decomposed into its constituent elemental sequences (from analysis of the combinational sequence). Embodiments of the present invention contemplate that the elemental sequences can be placed in the public domain and used without compromising the effective encrypting capability of the combinational sequence.
II. Related Art
Cryptography (the practice of encrypting and decrypting messages) probably dates back to shortly after man was first able to send written messages from person to person. The sender of the message would use some agreed-upon transformation (also in the receiver's possession) to encrypt the message before sending it to the receiver. The receiver would then use this transformation (hereafter referred to as a "key") to decrypt the message. This practice was particularly prevalent during times of conflict, when maintaining the secrecy of messages was a matter of life or death.
In recent years, messages (in, e.g., data, voice and video form) have been more and more frequently transmitted over wires and air waves. This mode of transmission makes messages more vulnerable to access by unauthorized persons, since the messages become accessible to anyone having the proper (and often easily obtainable) equipment. Since the rise of commercial espionage has led to much electronic snooping through these various message transmission corridors, the art of cryptography has become increasingly important.
Advances over the years in the development of complex and difficult-to-break encrypted messages have been closely followed by advances in code-breaking techniques, both of which owe much to the advancement of computational resources. This cycle has been fueled, of course, by the continued desires of unauthorized persons to read these messages. As a consequence, there has been a never-ending need to develop better ways to encrypt messages.
In general, an encrypted (i.e., enciphered) message is created by mathematically combining the original message with a key. When an encrypted message is received by the intended receiver, the receiver typically uses the same key to decrypt (i.e., decipher) the message (again, by some mathematical combination) as was used by the sender to encrypt it. Thus, the use of the term, "key" (that is, it "locks" and "unlocks" the message). Typically, the key is generated by some esoteric scheme.
To make an encrypted message secure, it is necessary to make the key with which the original message is combined as "random" as possible. In essence, the less the key comprises any discernable patterns, the greater its randomness. A feature of randomness of a sequence is that the value of a given character/digit in the sequence cannot be determined even with complete knowledge of the values of all other characters/digits in the sequence. One "cryptographic" definition of a random sequence is a sequence that has no measurable biases. That is, any such bias is much much smaller than the standard deviation of that distribution (the criterion becomes more severe as sequence length increases).
The degree of "randomness" in a sequence is often expressed in terms of its "entropy." This concept, which was borrowed from thermodynamics and first applied to communications in the 1940's by Claude Shannon of Bell Laboratories, is a measure of the disorder (that is, lack of organization and pattern) in a system. Consequently, the greater the degree of randomness in a sequence, the greater its entropy.
The efficient and rapid generation of "cryptographically random" (hereinafter "random") keys is an ongoing goal of cryptography. In generating these keys, complex, non-linear schemes are typically used. Such schemes can achieve a significant degree of efficiency (i.e., a relatively small amount of input is required to generate a relatively large output), but sacrifice randomness.
Obviously, whatever key is used to encrypt the message must also be in the possession of the receiver of the message so that it can be decrypted. Typically, the key is as long as the message being sent. Consequently, when persons are transmitting large amounts of message, then large amounts of key are required for the encryption/decryption process. Since it is vital that no key be reused in order to maintain the security of the encrypted message, new quantities of key must be continually generated. This is based upon the "one-time key" theory, which states that encrypting a message with a random key will yield a truly unbreakable encrypted message, but only if the key is used once. This is in contrast to the non-linear schemes mentioned above, since the one-time system sacrifices efficiency to produce a random key.
Transporting the key (or elemental sequences used to generate it) to each sending/receiving party is typically accomplished independently of the transmission of any messages. This is, of course, done so as not to compromise the secrecy of the messages (since divulgence of the key to unauthorized persons would compromise encryption). Thus, the step of distribution and subsequent protection of the key (or elemental sequences used to generate it) is both a logistic inconvenience as well as a possible source of compromise. For this reason, the ability for sending and receiving parties to independently generate the same long random key and minimize the distribution step would be advantageous.
Current non-linear techniques accomplish this by using a so-called Key Generator (KG) which uses much less information as input than is ultimately generated as key output (i.e., much "algorithmic compression"). This allows large quantities of key to be generated, but has the negative effect of generating only "pseudo-random" keys. These keys are defined as pseudo-random since, based upon the way they are generated, they inherently have embedded patterns (i.e., biases). Although these patterns may not be easily discernable (even by a creator of a KG) and are advertized as "defying analysis," such types of systems have historically been broken by the discovery of these patterns.
Even if reliable random sequences could be generated by a conventional KG device, there is still the problem of distributing (to each sender/receiver) the information to be used with the KG device to generate the same key for all parties involved. This problem could be minimized if the source(s) (that is, elemental sequences) from which keys were generated could be kept in the public domain. This would allow the senders/receivers to have independent access to a library of elemental sequences from which virtually unlimited amounts of random key could ultimately be created. Thus, all that senders/receivers would need to be agree upon is the elemental sequences that are to be used (rather than physically transferring the elemental sequences themselves) and the way that they are to be used.